package com.coder.algorithm.offer_2;

import java.util.Locale;

/**
 * 1～n 整数中 1 出现的次数
 *
 * @author yuhushuan
 * @date 2020/6/25 22:47
 */
public class _43_1_NumberOf1 {

    private static int numberOf1Between1AndN(int n) {
        if (n <= 0) {
            return 0;
        }
        // 将数字转成字符数组
        char[] str = Integer.toString(n).toCharArray();
        return numberOf1(str);
    }

    /**
     * 去除最高位数字（递归到最后一位）
     *
     * @param strN
     * @return
     */
    private static int numberOf1(char[] strN) {
        if (strN == null) {
            return 0;
        }
        for (int i = 0; i < strN.length; ++i) {
            if (strN[i] < '0' || strN[i] > '9') {
                return 0;
            }
        }

        int first = strN[0] - '0';
        int length = strN.length;

        // 如果只剩下一个数字，返回 1 的个数
        if (length == 1 && first == 0) {
            return 0;
        }
        if (length == 1 && first > 0) {
            return 1;
        }

        // 假设 strN 是 "21345"
        // numFirstDigit 是数字 10000 ～ 19999 的第一位中的数目
        int numFirstDigit = 0;// 默认值（first='0'时）
        if (first > 1) {
            numFirstDigit = powerBase10(length - 1);
        } else if (first == 1) {
            numFirstDigit = Integer
                    .parseInt(new String(strN, 1, length - 1)) + 1;
        }

        // numOtherDigits 是 01346 ～ 21345 除第一位之外的数位中的数目
        int numOtherDigits = first * (length - 1) * powerBase10(length - 2);
        // numRecursive 是 1～1345 中的数目
        int numRecursive = numberOf1(new String(strN, 1, length - 1).toCharArray());

        return numFirstDigit + numOtherDigits + numRecursive;
    }

    private static int powerBase10(int exponent) {
        int result = 1;
        for (int i = 0; i < exponent; ++i) {
            result *= 10;
        }
        return result;
    }

    private static int numberOf1Between1AndN_solution2(int n) {
        int number = 0;
        for (int i = 1; i <= n; ++i) {
            number += numberOf1_solution2(i);
        }
        return number;
    }

    private static int numberOf1_solution2(int n) {
        int number = 0;
        while (n != 0) {
            if (n % 10 == 1) {
                number++;
            }
            n = n / 10;
        }
        return number;
    }

    public static void main(String[] args) {
        // 功能测试
        print(5);
        print(10);
        print(55);
        print(99);

        // 边界值测试
        print(0);
        print(1);

        // 性能测试
        print(10000);
        print(12345);
        print(123456);
        print(1234567);
    }

    private static void print(int n) {
        System.out.println("从 1 到 " + n + " 的数字中出现 1 的次数");

        long nano = System.nanoTime();
        System.out.println(String.format(Locale.getDefault(),
                "解法一：%d，耗时 %d 纳秒",
                numberOf1Between1AndN(n), System.nanoTime() - nano));

        nano = System.nanoTime();
        System.out.println(String.format(Locale.getDefault(),
                "解法二：%d，耗时 %d 纳秒",
                numberOf1Between1AndN_solution2(n), System.nanoTime() - nano));
        System.out.println();
    }
}
